package alo.p6.work;

import org.junit.Test;
import alo.p6.BinaryTreeNode;
//二叉树直径
//树的直径（也叫作树的宽度）就是树中两个叶子结点之间的最长路径中的结点个数
//深度路径
public class DiameterOfTree {
    static int diameter=0;
    @Test
    public  void test(){
        int[] A={1,2,4,5,3,6,7};
        int[] B={4,2,5,1,6,3,7};
        BuildBinaryTree buildBinaryTree=new BuildBinaryTree();
        BinaryTreeNode root = buildBinaryTree.buildBinaryTree(B,A,0,6);
        diameterOfTree(root);
        System.out.println(diameter);//4
    }
    //方法返回值是Math.max(left,right)+1，但只是为了实现递归
    //最后的直径为diameter的值
    int diameterOfTree(BinaryTreeNode root){
        int left,right;
        if (root==null) return 0;
        left=diameterOfTree(root.getLeft());
        right=diameterOfTree(root.getRight());
        diameter=Math.max(diameter,left+right);
        return Math.max(left,right)+1;
    }
}
